Leetcode 105.从前序与中序遍历序列构造二叉树

题目描述：

根据一棵树的前序遍历与中序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出

1
2

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

链接：

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

题目分析

1.迭代

  我们知道，在前序遍历中，结点的顺序按照 [根结点 左子树 右子树] 的顺序排列。则在连续的两个结点之间的关系只有两种情况，一种是后面结点是前面结点的左孩子，一种是后面结点是前面结点本身或者某个祖先的右孩子。而这两情况，可以通过中序遍历加以区分。中序遍历中，结点的排列是按照 [左子树 根结点 右子树] 进行排列的，若是第一种情况，则两种遍历的顺序相反，第二种情况则相同。并且第二种情况中是哪个祖先的右子树呢？其实就是前序遍历和中序遍历不再相反的那一个结点，也即局部的根结点。结合这样的数据特点，我们选择栈这种数据结构。栈中存放的结点是 还没考虑过右孩子的结点。
  我们使用一个 inorderIndex 来表示当前中序遍历的下标。我们按前序遍历的顺序作为循环，前序遍历的第一个结点就是根结点，加入到栈中。开始检查栈顶结点是否是当前中序遍历的结点，如果不是，也即意味着是第一种情况，前序遍历到的结点是栈顶结点的左孩子（这个左孩子会比栈顶结点更早出现于中序遍历中，因此栈顶结点不会是当前中序遍历的结点），连接到树中，并将其入栈；如果是，则说明是第二种情况，这个时候我们要找到是哪个祖先的右孩子，开始出栈，同时中序遍历下标也开始右移，不断比对直到栈为空或者栈顶结点不再是中序遍历的结点，则说明该结点是栈顶结点的右子树了。上面说的两种情况可能有点复杂，我们用下面的树进行理解。

1
2
3
4
5
6
7
8
9

前序遍历 [1, 2, 3, 4, 5, 6, 7, 8]
中序遍历 [4, 3, 2, 6, 5, 7, 1, 8]
      1
     / \
    2   8
   / \
  3   5
 /   / \
4   6   7

  中序遍历的第一个数字是 4。前序遍历中 1 为根，2 是第一种情况，也即是 1 的左孩子（可以采用反证法，如果不是，则 2 只能为 1 的右孩子，且左孩子为空，这个时候中序遍历一定是 1 开始的）。同理，在前序遍历遇到 4 之前的所有数字都要入栈，也即栈中为 [1, 2, 3, 4]。
  遇到 4 之后，我们可以知道，4 是最左的孩子了。那么前序遍历的下一个数字 5 是哪个祖先的右孩子呢？在中序遍历中，这个祖先的右孩子是比祖先的祖先更早出现的（因为他们在祖先的祖先的左孩子中），因此我们找到中序遍历中比栈更早出现的结点即可。我们将 4 出栈；inorderIndex 右移，栈顶为 3，中序遍历也为 3，继续出栈；栈顶为 2，中序遍历为 2，继续出栈；栈顶为 1，而中序遍历为 6。这个时候，我们可以知道，6 就是在 2 的右孩子中了（2 是祖先，1 是祖先的祖先，6 所在的子树比 1 更早出现，是 2 的右孩子）。而前序遍历到的结点 5 就是 2 的右孩子的根（前序遍历的根最早出现），所以可以直接将其连接到 2 的右孩子中，然后将 5 入栈。
  这个时候的栈是 [1, 5]。又可以继续上面的过程，6 不是 5，是第一种情况，也即 5 的左孩子，连接并入栈。重复以上的过程就可以得到最终的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) return nullptr;
        stack<TreeNode*> stk;
        TreeNode *root = new TreeNode(preorder[0]);
        stk.push(root);
        int inorderIndex = 0;
        for(int i = 1; i < preorder.size(); i++){
            TreeNode *now = stk.top();
            if(inorder[inorderIndex] != now->val){
                now->left = new TreeNode(preorder[i]);
                stk.push(now->left);
            }
            else{
                while(!stk.empty() && stk.top()->val == inorder[inorderIndex]){
                    now = stk.top();
                    stk.pop();
                    inorderIndex++;
                }
                now->right = new TreeNode(preorder[i]);
                stk.push(now->right);
            }
        }
        return root;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们对前序遍历和中序遍历都进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。栈的最大元素个数为 $n$。

2.递归

  我们知道，前序遍历的结构是 [根结点, [左子树的前序遍历], [右子树的前序遍历]]，中序遍历的顺序是 [[左子树的中序遍历], 根结点, [右子树的中序遍历]]。可以发现，他们的定义是递归的，并且这三块中的内容也具有对应关系，左子树的前序遍历和中序遍历构造的树就是根结点的左子树，右子树同理。因此我们应该可以使用一个递归函数解决这个问题。
  递归的关键就是找到这三块内容的分界线。很容易可以想到利用根结点进行划分。前序遍历的第一个结点就是根结点，而我们在中序遍历中就可以根据根结点的值找到根结点的位置，划分好中序遍历后，再根据左子树序列的长度，可以划分前序遍历。为了提升寻找中序遍历中根结点的位置速度，我们给中序遍历建立了一个值和结点位置对应的哈希表。
  递归函数的返回值是一棵树，我们利用根结点新建结点，再递归调用函数建立左子树和右子树，然后向上层返回根结点即可。递归中止的条件也即结点为空。
  preorder[preLeft ~ preRight] 和 inorder[inLeft ~ inRight] 分别表示了前序遍历和中序遍历的区间。（代码是为了便于理解，实际上没有用到 inRight）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    unordered_map<int, int> inorderIndex;
    
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preLeft, int preRight, int inLeft, int inRight){
        if(preLeft > preRight) return nullptr;

        int rootVal = preorder[preLeft];
        int inRoot = inorderIndex[rootVal];
        int leftLength = inRoot - inLeft;
        TreeNode *root = new TreeNode(rootVal);
        root->left = build(preorder, inorder, preLeft + 1, preLeft + leftLength, inLeft, inRoot - 1);
        root->right = build(preorder, inorder, preLeft + leftLength + 1, preRight, inRoot + 1, inRight);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int size = inorder.size();
        for(int i = 0; i < size; i++){
            inorderIndex[inorder[i]] = i;
        }
        return build(preorder, inorder, 0, size - 1, 0, size - 1);
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们对中序遍历行了一次遍历建立哈希表，而在递归的过程中实际我们对前序遍历和中序遍历进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。哈希表的大小为 $n$，递归栈的最大深度也为 $n$。